1. Field of the Invention
The present invention relates to a data compression apparatus for compressing data such as image data, and a data compression program storage medium storing a data compression program, which causes an information processing apparatus such as a computer to operate as the data compression apparatus.
2. Description of the Related Art
Hitherto, in order to reduce storage capacity or traffic, there is widely adopted a technology of compressing data such as image data.
For example, Japanese Patent Laid Open Gazette TokuKai Hei. 5-328142 discloses a technology as set forth below.
When a CLUT (color lookup table) is constructed through selection of a representative color from an original image, color numbers are allotted so that a series of color numbers has a closed value of color data, and then a bit map associated with the CLUT is created to determine a difference of color numbers between adjacent pixels. In the event that the difference takes a large value, the color number of the bit map is altered in such an extent that no deterioration of image quality occurs, so that the difference is biased to a small value, and a run length coding is applied to difference data.
Japanese Patent Laid Open Gazette TokuKai Hei. 10-164620 discloses a technology as set forth below.
Image data consisting of a plurality of data allotted to the associated colors is encoded on a non-reversible compression basis. One of the data is allotted to a transparent color, which is reversible. The image data comprises an immediate value (a first value in differential coding) and a plurality of differential values (a previous value in differential coding) subsequent to the immediate value. When those values are encoded on a non-reversible compression basis, the immediate value and the differential values representative of the transparent color are provided on a reversible basis. And the immediate value representative of the transparent color is expressed by an intermediate value of the data values for respective colors, or the differential values representative of the transparent color is expressed by “0”.
Japanese Translation of PCT International Application No. 2001-520822 discloses a technology in which encoding is carried out by a difference between the predicted number (s′ (j)) and the actual number (s (j)).
Japanese Patent Laid Open Gazette TokuKai Hei. 9-200540 discloses an image compression apparatus in which for Nth line of pixel data train, the state of distributions of the same pixel data in the sub-scanning direction is recognized, and the state of distributions of the same pixel data in the main scanning direction is recognized, so that it is decided in accordance with the results of those recognition whether the same pixel data continued in the sub-scanning direction are to be subjected to a compression processing, or the same pixel data continued in the main scanning direction are to be subjected to a compression processing.
Here, there will be explained a system to which a data compression technology is applied.
FIG. 1 is a view useful for understanding an example of a print system to which a data compression technology is applied. FIG. 2 is a view useful for understanding a data processing in the print system.
As shown in FIG. 1, the print system comprises a host controller 100, an interface equipment 200, and a printer 300. The host controller 100 is connected to the interface equipment 200 via an all-purpose interface cable 150 such as SCSI. And the interface equipment 200 is connected to the printer 300 via a dedicated interface cable 250.
In the host controller 100, as shown in FIG. 2, data 11 of images and characters described in various languages and formats, such as PDF, PS, TIFF, are divided into image (CT; Continuous Tone) data and characters and lines (LW; Line Work) data, and RIP (Raster Image Processing) is applied to such two types of data, so that bit map data 12A and 13A are created. Further, data compression processing is applied to such two types of data, so that non-reversible compression data 14 is created on the CT and reversible compression data 15 is created on the LW. Those types of compression data 14 and 15 are transmitted from the host controller 100 via the all-purpose interface cable 150 shown in FIG. 1 to the interface equipment 200. The interface equipment 200 applies a data expansion processing to the transmitted compression data 14 and 15 to creates bit map data 12B and 13B associated with the bit map data 12A and 13A, respectively, which are in the state before an application of the data compression processing by the host controller 100. With respect to the CT data, when the host controller 100 performs the data compression, the non-reversible compression processing is carried out. Accordingly, it is difficult to completely return the CI data after the data expansion, or the bit map data 12B to the CI data before the data compression, or the bit map data 12A. However, it is possible to reproduce the substantially same bit map data. With respect to the LW data, when the host controller 100 performs the data compression, the reversible compression processing is carried out. Accordingly, it is possible to restore the LW data after the data expansion, or the bit map data 13B to the LW data before the data compression, or the bit map data 13A.
The interface equipment 200 synthesizes the CI data after the data expansion or the bit map data 12B with the LW data after the data expansion or the bit map data 13B, and transmits the synthesized data to the printer 300 together with halftone dot information and the like in form of a tag. The printer 300 prints out an image in accordance with the bit map data received from the interface equipment 200 and the attached tag information.
In the event that there is a need that the host controller 100 and the interface equipment 200 are individually constructed in form of a separated apparatus, for example, in a case where the host controller 100 and the interface equipment 200 are mutually isolated, and in case of a system in which the interface equipment 200 receives image data from a plurality of host controllers, as shown in FIG. 2, there is provided such an arrangement that data is transferred to the interface equipment 200 through data compression by the host controller 100, so that the interface equipment 200 performs data expansion. This arrangement makes it possible to reduce a transfer time of the data from the host controller 100 to the interface equipment 200, and thereby improving the productivity of the print.
Generally, with respect to the CT data, there is adopted compression system such as JPEG, which is high in compressibility, while it is non-reversible. On the other hand, with respect to the LW data, there is adopted reversible compression system such as PackBits.
Hereinafter, for a comparison with the embodiments of the present invention, there will be described an encoding system by PackBits.
FIG. 3 is an explanatory view for a PackBits coding system.
It is assumed that “01, 02, 02, 02, 03, 03, 03, 03, 04, 05”, which appear at the upper stage, denote the original data. Where there is adopted a hexadecimal notation. Of the original data, the first numerical value is “01”, and the second numerical value is “02”, and the third numerical value is also “02”. The numerical value “02” is continued in the same numerical value. Thus, only the numerical value “01” is not continued.
Thus, there is established a numerical value “00” (the first numerical value “00” appearing at the lower stage in FIG. 3) wherein a number 1 is subtracted from the discontinuous numerical value (here “1”). Subsequently, there is established the discontinuous numerical value (here “01”), that is, the second numerical value “01” appearing at the lower stage in FIG. 3). In other words, the original data “01” is replaced by “00 01” in accordance with PackBits coding.
Next, since “02” of the original data continues by three pieces, there is established “FE” wherein a number (here 2), which is obtained through a subtraction of one from the continued number (here 3), is expressed in minus, and the negative number (here −2) is expressed by the hexadecimal notation (the third numerical value “FE” appearing at the lower stage in FIG. 3), and thereafter the continuous numerical number (here “02”) itself is established (the fourth numerical value “02” appearing at the lower stage in FIG. 3). In other words, “02 02 02” of the original data is replaced by “FE 02” in accordance with PackBits coding.
Next, since “03” of the original data continues by four pieces, in a similar fashion as mentioned above, there is established “FD” wherein a number (here 3), which is obtained through a subtraction of one from the continued number (here 4), is expressed in minus, and the negative number (here −3) is expressed by the hexadecimal notation, and thereafter the continuous numerical number (here “03”) itself is established. In other words, “03 03 03 03” of the original data is replaced by “FD 03” in accordance with PackBits coding.
Further, thereafter, “04 05” of the original data continue. However, those numerical numbers “04” and “05” do not continue in the same number. Thus, there is established a numerical value “01”, which is obtained through a subtraction of one from a number (here 2) of the discontinued numerical values (“04”, “05”), and then the discontinued numerical values itself “04 05” are established. In other words, “04 05” of the original data is replaced by “01 04 05” in accordance with PackBits coding.
In PackBits, the coding is performed in accordance with the above-mentioned rule.
In case of the PackBits coding, the number, which is capable of being established as the continuous number of the same numerical value, is −1 to −127. That is, the number, which is capable of being expressed in form of the continuous number, is up to 128. This number is expressed by 2 bytes (8 bits×2), and thus the maximum bulk compressibility is 2/128= 1/64 on a principle basis.
However, for example, in case of the LW data, it often happens that the same numerical values are continued, for instance, the continued blank, and this brings about a problem that the maximum bulk compressibility 1/64 is inefficient.
As seen from FIG. 3, the original data “01” is encoded into “00 01”, and the original data “04 05” is encoded into “01 04 05”. In those cases, the encoded data is more redundant than the original data.
While the explanation of FIG. 3 is concerned with multiple-valued data, such as “01”, “02”, “03”, “04”, “05”, . . . , the LW data is often concerned with binary data, for example, in case of the LW data representative of an image consisting of only characters each having the same density on a white background for instance.